from LeetCoder import *


class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        mx = 0
        diff = [0] * (n + 1)
        mxs = [0] * (2 * n + 2)

        def dfs(root, sum):
            if root > n:
                return 0
            sum += cost[root - 1]
            nonlocal mx
            mx = max(mx, sum)
            v1 = dfs(root * 2, sum)
            v2 = dfs(root * 2 + 1, sum)
            diff[root] = abs(v1 - v2)
            mxs[root] = max(v1, v2) + cost[root - 1]
            return mxs[root]
        dfs(1, 0)
        ans = 0

        def dfs2(root, sum):
            if root > n:
                return
            sum += cost[root - 1]
            cur = max(mxs[root * 2], mxs[root * 2 + 1])
            add = mx - sum - cur
            nonlocal ans
            ans += add
            dfs2(root * 2, sum + add)
            dfs2(root * 2 + 1, sum + add)
        dfs2(1, 0)
        return ans


s = Solution()
print(s.minIncrements(n=7, cost=[1, 5, 2, 2, 3, 3, 1]))
